"""
quick sort
快速排序（修正版）
- 修复基准数交换逻辑漏洞
- 支持重复元素、空列表、单元素列表等边界情况
- 保持原地排序，空间复杂度 O(log n)（递归栈）
"""

def partition(nums: list[int], left: int, right: int) -> int:
    # 选择左边界作为基准数（也可优化为随机选择，避免最坏情况）
    pivot = nums[left]
    i = left  # 左指针（从基准数后开始）
    j = right  # 右指针

    while i < j:
        # 1. 先从右向左找：首个小于基准数的元素（必须先移动j，确保相遇时j指向小于等于pivot的元素）
        while i < j and nums[j] >= pivot:
            j -= 1
        # 2. 再从左向右找：首个大于基准数的元素
        while i < j and nums[i] <= pivot:
            i += 1
        # 3. 交换两个元素（此时i<j，且nums[i]>pivot、nums[j]<pivot）
        nums[i], nums[j] = nums[j], nums[i]
    
    # 4. 基准数归位：交换基准数和j（此时i=j，且nums[j]<=pivot）
    nums[left], nums[j] = nums[j], nums[left]
    return j  # 返回基准数的最终索引


def quick_sort(nums: list[int], left: int = None, right: int = None) -> list[int]:
    # 初始化左右边界（首次调用时无需手动传入left和right）
    if left is None:
        left = 0
    if right is None:
        right = len(nums) - 1
    
    # 递归终止条件：子数组长度<=1
    if left >= right:
        return nums
    
    # 分区操作，得到基准数的索引
    pivot_index = partition(nums, left, right)
    # 递归排序左子数组（基准数左侧）
    quick_sort(nums, left, pivot_index - 1)
    # 递归排序右子数组（基准数右侧）
    quick_sort(nums, pivot_index + 1, right)
    
    return nums  # 方便链式调用（原地排序，返回自身不额外占用空间）


if __name__ == '__main__':
    # 测试用例（覆盖重复元素、无序、边界情况）
    test_cases = [
        [87, 11, 23, 18, 18, 23, 11, 56, 87, 56],  # 含重复元素
        [],  # 空列表
        [5],  # 单元素
        [3, 1, 2],  # 简单无序
        [9, 8, 7, 6, 5],  # 逆序
        [1, 2, 3, 4, 5],  # 已有序
    ]
    
    for idx, case in enumerate(test_cases, 1):
        sorted_case = quick_sort(case.copy())  # 复制避免修改原列表
        print(f"测试用例{idx}：{case} → {sorted_case}")